package com.cet.algorithm.栈与队列;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * @program: algorithm
 * @description: 前K个高频元素
 * @author: 陈恩涛
 * @create: 2022-07-13 15:37
 **/
public class LC347 {

    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 2, 2, 3};
        for (int i : topKFrequent(nums, 2)) {
            System.out.println(i);
        }
    }

    public static int[] topKFrequent(int[] nums, int k) {
        final int[] result = new int[k];
        // 优先队列，默认实现为小顶堆
        final PriorityQueue<Map.Entry<Integer, Integer>> priorityQueue = new PriorityQueue<>(Comparator.comparing(Map.Entry::getValue));

        final Map<Integer, Integer> map = new HashMap<>();


        for (int num : nums) {
            final Integer value = map.getOrDefault(num, 0);
            map.put(num, value + 1);
        }

        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            priorityQueue.offer(entry);
            if (priorityQueue.size() > k) {
                priorityQueue.poll();
            }
        }

        for (int i = k -1 ; i >= 0; i--) {
            result[i] = priorityQueue.poll().getKey();
        }

        return result;
    }
}
